package william.list;

/**
 * @author ZhangShenao
 * @date 2024/1/14
 * @description <a href="https://leetcode.cn/problems/intersection-of-two-linked-lists/description/">...</a>
 */
public class Leetcode160_相交链表 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 首先计算出两个链表长度的差值diff
     * 然后通过双指针同时遍历两个链表
     * 将较长的链表从头节点开始,跳过diff个节点
     * 最后同时遍历两个链表,直到两个指针相遇,即为相交节点
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //边界条件校验
        if (headA == null || headB == null) {
            return null;
        }

        //首先计算出两个链表长度的差值diff
        ListNode longHead;
        ListNode shortHead;
        int diff = 0;
        int lengthA = 0;
        int lengthB = 0;
        ListNode n = headA;
        while (n != null) {
            lengthA++;
            n = n.next;
        }
        n = headB;
        while (n != null) {
            lengthB++;
            n = n.next;
        }

        if (lengthA >= lengthB) {
            longHead = headA;
            shortHead = headB;
            diff = lengthA - lengthB;
        } else {
            longHead = headB;
            shortHead = headA;
            diff = lengthB - lengthA;
        }

        //通过双指针同时遍历两个链表
        //首先将长链表跳过diff个节点
        for (int i = 0; i < diff; i++) {
            longHead = longHead.next;
        }

        //同时遍历两个链表,直到两个指针相遇,即为相交节点
        while (longHead != null && shortHead != null) {
            if (longHead == shortHead) {
                return longHead;
            }
            longHead = longHead.next;
            shortHead = shortHead.next;
        }

        //边界条件:未找到相交节点
        return null;
    }
}
